class Solution(object):
    def countSpecialSubsequences(self, nums):
        base = 10 ** 9 + 7
        n = len(nums)
        ans = 0
        DP = [[0 for _ in range(3)] for _ in range(n)]
        if nums[0] == 0:
            DP[0][0] = 1
        for i in range(1, n):
            if nums[i] == 0:
                DP[i][0] = 2 * DP[i - 1][0] + 1
            else:
                DP[i][0] = DP[i - 1][0]
            if nums[i] == 1:
                DP[i][1] = DP[i - 1][0] + 2 * DP[i - 1][1]
            else:
                DP[i][1] = DP[i - 1][1]
            if nums[i] == 2:
                ans = (ans + DP[i - 1][1] + DP[i - 1][2]) % base
                DP[i][2] = 2 * DP[i - 1][2] + DP[i - 1][1]
            else:
                DP[i][2] = DP[i - 1][2]
        return ans

                

data = Solution()
nums = [0,1,2,2]
print(data.countSpecialSubsequences(nums))